package algorithm_demo.demo03;

/**
 * 判断二叉树是否是搜索二叉树
 * <p>
 * 每一棵子树的左树都比头小，右树都比头大
 * <p>
 * 对于每棵树的头X，满足以下三点即为平衡二叉树
 * <p>
 * x左树搜索二叉树
 * <p>
 * x右树搜索二叉树
 * <p>
 * x的值大于左树最大值，x的值小于右树最小值
 *
 * @author Api
 * @date 2023/2/12 9:21
 */
public class Code02_IsBST {
    public static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class Info {
        public boolean isBST;
        public int min;
        public int max;

        public Info(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    public static boolean isBST(Node x) {
        return process(x).isBST;
    }

    public static Info process(Node x) {
        if (x == null) {
            return null; //如果这里直接返回null，则下面需要单独判断null
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        //开始组装Info
        int min = x.value;
        int max = x.value;
        if (leftInfo != null ){
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
        }
        if (rightInfo != null){
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
        }
        boolean isBST = true;
        if (leftInfo != null && !leftInfo.isBST){
            isBST = false;
        }
        if (rightInfo != null && !rightInfo.isBST){
            isBST = false;
        }
        if (leftInfo != null && leftInfo.max >= x.value){
            isBST = false;
        }
        if (rightInfo != null && rightInfo.min <= x.value){
            isBST = false;
        }
        return new Info(isBST, max, min);
    }

    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3);
        root.right = new Node(7);
        root.left.left = new Node(1);
        root.left.right = new Node(4);
        root.left.left.left = new Node(0);
        root.left.left.right = new Node(2);
        root.right.left = new Node(6);
        root.right.right = new Node(8);
        root.right.right.right = new Node(9);

        boolean bst = isBST(root);
        System.out.println(bst);
    }


}
